The present invention is directed to mobile ad hoc networks (MANETs). More specifically, the present invention is directed to a system and method for geocasting data packets in a MANET.
A MANET is a network of mobile wireless terminals, such as wireless phones, that communicate with each other within a given region or area. A MANET does not require or use “base station” terminals to control the communications between the wireless terminals. Each wireless terminal is capable of receiving/transmitting data packets to/from other wireless terminals in the MANET.
In a MANET, when a wireless terminal intends to send the same information to more than one destination (i.e., more than one wireless terminal recipient), it will typically broadcast (i.e., transmit the information so that any terminal within range can receive it) or multicast (i.e., a series of broadcasts from terminal to terminal through the network) the information instead of transmitting a series of unicasts (i.e., a separate transmission to each intended recipient). In a traditional broadcast, the broadcasting wireless terminal will transmit the information once and hope that all the intended recipients are in range to receive the transmission. The intended recipients that are outside the range of the broadcasting terminal, however, will not be able to receive the message. Another technique such as multicasting would have to be used to get the message to such remote terminals.
In a conventional multicast, the intended recipients register to a predetermined group address. The originating (sending) wireless terminal will address the message to the group address and transmit the message once. The message will then be passed or retransmitted from wireless terminal to wireless terminal (multicast) throughout the MANET so that all the group members have a chance of receiving the multicast message no matter where they are located. Multicasting has been found to be a much more effective technique than broadcasting when intended recipients are located outside the range of the originating wireless terminal.
Although multicasting, and in some cases broadcasting, are effective when the intended recipients are scattered throughout the MANET, they are not efficient for applications where the intended recipients are all located in a defined physical area. For example, when trying to send messages to everyone in a disaster area or all troops in a given battle venue, multicasting can result in utilizing the processing power of the MANET for many unnecessary transmissions. That is, multicasting may result in multiple retransmission or rebroadcasts by wireless terminals that are not the intended recipients and by Wireless terminals that are located in areas remote from the disaster area or the battle venue. Moreover, due to the fact that mobile terminals move often and unpredictably, it is impractical to maintain a (registered) multicast group for each arbitrary geographic region. As a result, for such applications, a technique called geographical broadcasting, or geocasting, is preferred.
The basic idea of a geocast is to send a packet to every node geographically positioned within a specified region called a geocast region. The set of wireless terminals in the geocast region are referred to as the geocast group. If a wireless terminal resides in the geocast region it will automatically become a member of the corresponding geocast group, and thus no registration is necessary (as in conventional multicasting). A wireless terminal may therefore send a message to every wireless terminal in the geocast group by addressing the message to the geocast region.
One approach that has been proposed for geocasting in a MANET is a technique called location-based flooding. Geocasting through location-based flooding requires that the wireless terminals in the MANET are equipped with the ability to determine their own location using, for example, a Global Positioning System (GPS), and are able to determine the coordinates that define the geocast region (typically from a geographic “address” within the data packet itself). The wireless terminal initiating or originating the communication will address the packets to include its own location coordinates and a description of the geocast region, and then broadcast the packets to its neighboring wireless terminals. Each neighboring wireless terminal will then compare the geocast region coordinates to its own location. If its location is within the specified geocast region, it will accept the packet, process it, and may also decide to rebroadcast, or retransmit, the packet to its neighboring wireless terminals. If the wireless terminal's location is outside the geocast region, the wireless terminal will not process the packet but may decide to retransmit the packet in order to further propagate the packet to wireless terminals that may not as yet have received the packet. If the wireless terminal decides to retransmit, the wireless terminal will typically include its own location information in the retransmitted packet. This process may be repeated as the packet is retransmitted through the MANET.
In such present-day systems, the decision whether to retransmit is typically made based upon rules or heuristics that may take into account from how far away the received packet was transmitted. To do this, the wireless terminal that receives the packet compares its present geographical location to the geographical location of the sending wireless terminal (obtained from the location information in the packet). Packets that have been received from sending terminals that are located no closer than some minimum distance away are retransmitted. All other packets may be dropped.
Although such present-day algorithms are robust, they are not efficient for geographically large MANETs. In geographically large MANETs, such algorithms may result in the packets traveling paths having many “hops” and therefore taking a long time to be transmitted from source to destination. In addition, when the MANET includes a large number of wireless terminals in an extended area, such algorithms tend to result in many unnecessary retransmissions, wasting the resources of the MANET.
Additionally, current geocasting algorithms often have trouble in certain environments. For example, the maze-like characteristics of city-style geometries present difficulties, typically due to the need for precise selection of relay points.